Switched network elements, such as layer 2 switches, layer 3 routers, or any other type of switch that switches packets between input and output ports, maintain either input queues, output queues, or both to control the switching of packets to and from the network. For example, in an output-buffering switch, packets that arrive at the switch are classified according to the packet type and quality of service and are stored in an output queue to be scheduled in accordance with a variety of parameters, e.g. priority, bandwidth or relative time at which the particular queue was last serviced. Once the queue entry associated with the packet is scheduled, the packet is forwarded to an output port and sent over a network. In an input-buffering switch, packets may be queued at the input ports, scheduled, and forwarded to output ports for outbound transmission.
One mechanism for determining when a particular queue should be scheduled includes defining a bandwidth state for the queue. As used herein, the term “bandwidth state” refers to a state that indicates whether bandwidth being consumed by a particular queue is less than or greater than allocated bandwidth values for that queue. For example, a queue may be allocated minimum and maximum bandwidth values. The minimum bandwidth value may indicate a minimum guaranteed bandwidth that is to be allocated to the queue. The maximum bandwidth value may indicate a bandwidth that should not be exceeded.
Using the minimum and maximum bandwidth values, several states can be defined for a queue and the states can be used to control scheduling of the queue. For example, one state may indicate that the bandwidth currently being consumed by a queue is less than the minimum allocated bandwidth value. If the bandwidth currently being consumed is less than the minimum bandwidth value, the queue should be scheduled with high priority, so that bandwidth will increase to the minimum value. Another state may indicate that the bandwidth currently being consumed by a queue is between the minimum and maximum bandwidth values. In this state, the queue should be scheduled with low priority, since the level of service being provided to the queue is within the allocated bandwidth values. Yet another state may indicate that the bandwidth currently being consumed by the queue is greater than the maximum bandwidth value. In this bandwidth state, the queue should not be scheduled, since the queue is currently consuming more than its allocated bandwidth.
In order to properly schedule queues using bandwidth state, it is necessary to accurately measure the current bandwidth being consumed by a queue. One method for measuring the bandwidth consumed by a queue is to use token buckets. A token bucket is a hardware- or software-implemented algorithm that allows packets to be scheduled based on the number of tokens available in a token bucket. Tokens in the token bucket are refreshed at a predetermined rate. As long as there are sufficient tokens available in the token bucket, packets can be transmitted. If the bucket is empty or contains an insufficient number of tokens, packets waiting to be transmitted may be queued until sufficient tokens are present in the token bucket to allow the packet to be transmitted.
FIG. 1 is an example of a token bucket. In FIG. 1, a token bucket 100 stores a number of tokens referred to as a token count. Token bucket 100 is filled at a refresh rate R. A start threshold T that is greater than the maximum packet size is associated with the token bucket. For packets to be transmitted the number of tokens should be greater than or equal to T. The size of token bucket 100 may be set to a predetermined value based on an anticipated packet burst threshold.
When a queued packet 102 arrives at token bucket 100, queued packet 102 is transmitted if the token count in token bucket 100 is greater than T. In this example and in all of the remaining examples described herein, it is assumed that one token corresponds to one byte of transmitted data. Assuming T equals 1500 bytes, if queued packet 102 has 64 bytes of data, and there are at least 1500 tokens in token bucket 100, queued packet 102 will be transmitted as transmitted packet 104. The token count in token bucket 100 will then be decremented by 64 tokens.
In some network switch implementations, token buckets may be associated with queues that are associated with output ports. In one implementation, each queue may have a minimum token bucket and a maximum token bucket. The minimum token bucket contains tokens that are used to guarantee a minimum bandwidth value. The maximum token bucket contains tokens that are used to provide a maximum bandwidth value that should not be exceeded.
FIGS. 2A and 2B illustrate the use of minimum and maximum token buckets to control bandwidth provided to a queue. Referring to FIG. 2A, a minimum token bucket 200 contains 1560 tokens and a maximum token bucket 202 contains 1565 tokens at a time when a sixty-four-byte packet 204 arrives in an output queue with which the token buckets are associated. Referring to FIG. 2B, when sixty-four-byte packet 204 is transmitted as transmitted packet 206, sixty-four tokens are removed from each token bucket. In the illustrated example, minimum token bucket 200 now has 1496 tokens and maximum token bucket 202 now has 1501 tokens.
The number of tokens in the minimum and maximum token buckets may be used to determine the bandwidth state of a queue. For example, in FIG. 2A, since both token buckets have tokens greater than 1500, the bandwidth state of the queue is that the bandwidth currently being consumed by the queue is less than the minimum bandwidth. Accordingly, the queue would be scheduled with high priority. In FIG. 2B, since minimum token bucket 200 has less than 1500 tokens, and maximum token bucket 202 contains greater than 1500 tokens, the bandwidth currently being provided to the queue is between the minimum and maximum bandwidth values. Accordingly, the queue would be scheduled with low priority.
Since the bandwidth being provided to a queue depends on the number of tokens in the token bucket, it is desirable to control the token bucket refresh rate in order to provide the desired bandwidth. However, available literature on token buckets does not specify how to set a token bucket refresh rate in order to archive a desired bandwidth value. In addition, an end user of a switched network element may desire to specify bandwidth in standard denominations, such as kilobits per second, rather than token bucket refresh rates. Current literature on token buckets likewise does not specify how to convert standard bandwidth denominations into token bucket refresh rates. For example, Perros, An Introduction to ATM Networks, John Wiley and Sons, (2001) states that token buckets can be used for admission control in ATM networks. However, details on converting bandwidth values to token bucket refresh rates are not provided.
It may also be desirable to allow a user to specify bandwidth in any increments that the user desires. For example, a user receiving one megabit per second of bandwidth may desire to change the bandwidth allocation to a particular queue to 1.5 megabits per second. Assuming a refresh rate of one token per refresh interval achieves a bandwidth of one megabit per second, it would be necessary to provide 1.5 tokens per refresh interval to achieve 1.5 megabits per second. However, since a token is assumed to be an atomic entity that cannot be divided into fractions, one possible solution is to provide three tokens during a first token bucket refresh interval, 0 tokens during a second refresh interval, and continuously repeat this pattern. Providing three tokens during the first refresh interval and 0 tokens during the second refresh interval would achieve the desired average bandwidth value of 1.5 megabits per second. However, traffic output from the queue would be bursty, since all of the tokens would be provided during the first refresh interval. This burstiness problem increase as incremental bandwidth allocation requires additional token bucket refresh intervals to be used. For instance, if the desired bandwidth is 1.1 megabits per second, 11 tokens may be refreshed during the first refresh interval, followed by 9 intervals with zero refreshes. Such an allocation scheme would allow incremental bandwidth allocation, but would further increase burstiness.
Accordingly, in light of these deficiencies associated with token-bucket-based scheduling algorithms, there exists a need for improved methods and systems for fine grain bandwidth allocation without burstiness in a switched network element.